import java.util.Stack;

public class ExchangeSort {
    //实现冒泡排序
    public static void bubbleSort(int[] array){
        for(int i=0;i<array.length-1;i++){
            for(int j=0;j< array.length-1-i;j++){
                if(array[j]>array[j+1]){
                    //若前一个元素比后一个元素大则交换
                    int tmp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=tmp;
                }
                //完成一次循环，此时数组中最大值被“冒泡”至数组末端
            }
        }
    }

    //实现冒泡排序的优化形式
    public static void bubbleSort2(int[] array){
        for(int i=0;i<array.length-1;i++){
            //设定标志位判断是否在一次循环中发生了交换
            boolean flg=false;
            for(int j=0;j< array.length-1-i;j++){
                if(array[j]>array[j+1]){
                    //若前一个元素比后一个元素大则交换
                    int tmp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=tmp;
                    flg=true;
                }
                //完成一次循环，此时数组中最大值被“冒泡”至数组末端

                //判断标志位是否被置为true，若未被置为true则说明没有发生交换，整个数组有序，直接中断循环即可
                if(!flg){
                    break;
                }
            }
        }
    }

    //实现Hoare形式快速排序
    public static void hoareQuickSort(int[] array){
        //调用快速排序的底层方法
        hoareQuickSortChild(array,0,array.length-1);
    }

    //Hoare形式快速排序的底层递归方法（使用递归时要求递归有以下三个参数，为保证接口统一性，在快速排序方法中调用此递归方法即可
    private static void hoareQuickSortChild(int[]array,int start,int end){
        //递归的结束情况
        if(start>=end){
            return;
        }
        //通过基准值对该组元素进行分组，并获取基准值下标
        int par=hoarePartition(array,start,end);
        //递归左侧元素
        hoareQuickSortChild(array,start,par-1);
        //递归右侧元素
        hoareQuickSortChild(array,par+1,end);
    }

    //递归时用到的Hoare形式分组方法
    private static int hoarePartition(int[]array,int start,int end){
        //记录基准值位置下标
        int i=start;
        //将该组元素的起始元素作为基准值
        int tmp=array[start];
        while(start<end){
            //从末端开始遍历数组，直到找到比基准值小的元素的下标
            //start<end目的是防止下标越界
            //取大于等于或者小于等于的目的是防止进入死循环
            //先走末端因为若先走始端会出现相遇的地方为比基准值大的情况
            while(start<end && array[end]>=tmp){
                end--;
            }
            //从始端开始遍历数组，直到找到比基准值大的元素的下标
            while(start<end && array[start]<=tmp){
                start++;
            }
            //两次循环结束说明分别在始端找到比基准值大的元素以及在末端找到比基准值小的元素,二者交换
            int tmp1=array[start];
            array[start]=array[end];
            array[end]=tmp1;
        }
        //start和end相遇，将基准值和相遇处元素交换，使得中间为基准值，左侧为都比基准值小的元素，右边都为比基准值大的元素
        int tmp2=array[start];
        array[start]=array[i];
        array[i]=tmp2;
        //返回基准值下标
        return start;

    }

    //实现挖坑法形式快速排序
    public static void holeQuickSort(int[] array){
        //调用快速排序的底层方法
        holeQuickSortChild(array,0,array.length-1);
    }

    //快速排序的底层递归方法（使用递归时要求递归有以下三个参数，为保证接口统一性，在快速排序方法中调用此递归方法即可
    private static void holeQuickSortChild(int[]array,int start,int end){
        //递归的结束情况
        if(start>=end){
            return;
        }
        //通过基准值对该组元素进行分组，并获取基准值下标
        int par=holePartition(array,start,end);
        //递归左侧元素
        holeQuickSortChild(array,start,par-1);
        //递归右侧元素
        holeQuickSortChild(array,par+1,end);
    }

    //递归时用到的挖坑法形式分组方法
    private static int holePartition(int[]array,int start,int end){
        //将该组元素的起始元素作为基准值
        int tmp=array[start];
        while(start<end){
            //从末端开始遍历数组，直到找到比基准值小的元素的下标
            //start<end目的是防止下标越界
            //取大于等于或者小于等于的目的是防止进入死循环
            //先走末端因为若先走始端会出现相遇的地方为比基准值大的情况
            while(start<end && array[end]>=tmp){
                end--;
            }
            //直接从末端向始端的“坑”赋值填数
            array[start]=array[end];
            //从始端开始遍历数组，直到找到比基准值大的元素的下标
            while(start<end && array[start]<=tmp){
                start++;
            }
            //直接从始端向末端的“坑”赋值填数
            array[end]=array[start];
        }
        //start和end相遇，将基准值填入最后一个“坑”
        array[start]=tmp;
        //返回基准值下标
        return start;
    }

    //实现前后指针形式快速排序
    public static void pointerQuickSort(int[] array){
        //调用快速排序的底层方法
        pointerQuickSortChild(array,0,array.length-1);
    }

    //快速排序的底层递归方法（使用递归时要求递归有以下三个参数，为保证接口统一性，在快速排序方法中调用此递归方法即可
    private static void pointerQuickSortChild(int[]array,int start,int end){
        //递归的结束情况
        if(start>=end){
            return;
        }
        //通过基准值对该组元素进行分组，并获取基准值下标
        int par=pointerPartition(array,start,end);
        //递归左侧元素
        pointerQuickSortChild(array,start,par-1);
        //递归右侧元素
        pointerQuickSortChild(array,par+1,end);
    }

    //递归时用到的前后指针形式分组方法
    private static int pointerPartition(int[]array,int start,int end){
        //设定前后指针
        int pre=start;
        int suc=start+1;
        //以下算法实现：当suc遇到比基准值（始端元素）小的元素，前后指针均后移;遇到比基准值大的元素时，后指针先一直后移找到后面第一个比基准值小的元素，前指针再后移一位指向第一个比基准值大的元素，两指针所指元素交换
        while(suc<=end){
            if(array[suc]<array[start] && array[++pre]!=array[suc]){
                int tmp=array[pre];
                array[pre]=array[suc];
                array[suc]=tmp;
            }
            suc++;
        }
        //循环结束后前指针所在位置左侧都比基准值小，右侧都比基准值大,将基准值换到此位置
        int tmp=array[pre];
        array[pre]=array[start];
        array[start]=tmp;
        return pre;
    }

    //实现Hoare型快速排序的优化形式
    public static void hoareQuickSort2(int[] array){
        //调用快速排序的底层方法
        hoareQuickSortChild2(array,0,array.length-1);
    }

    //Hoare形式快速排序的底层递归方法（使用递归时要求递归有以下三个参数，为保证接口统一性，在快速排序方法中调用此递归方法即可
    private static void hoareQuickSortChild2(int[]array,int start,int end){
        //递归的结束情况
        if(start>=end){
            return;
        }
        //调用获取中位数下标的方法
        int index=midThreeNum(array,start,end);
        //将中位数放置在该组元素起始位置作为基准值，实现优化
        int tmp=array[index];
        array[index]=array[start];
        array[start]=tmp;
        //通过基准值对该组元素进行分组，并获取基准值下标
        int par=hoarePartition2(array,start,end);
        //递归左侧元素
        hoareQuickSortChild2(array,start,par-1);
        //递归右侧元素
        hoareQuickSortChild2(array,par+1,end);
    }

    //获取中位数下标的底层方法
    private static int midThreeNum(int[]array,int start,int end){
        int mid=(start+end)/2;
        if(array[start]<array[end]){
            if(array[mid]<array[start]){
                return start;
            }else if(array[mid]>array[end]){
                return end;
            }else{
                return mid;
            }
        }else{
            if(array[mid]<array[end]){
                return end;
            }else if(array[mid]>array[start]){
                return start;
            }
            else{
                return mid;
            }
        }
    }

    //递归时用到的Hoare形式分组方法
    private static int hoarePartition2(int[]array,int start,int end){
        //记录基准值位置下标
        int i=start;
        //将该组元素的起始元素作为基准值
        int tmp=array[start];
        while(start<end){
            //从末端开始遍历数组，直到找到比基准值小的元素的下标
            //start<end目的是防止下标越界
            //取大于等于或者小于等于的目的是防止进入死循环
            //先走末端因为若先走始端会出现相遇的地方为比基准值大的情况
            while(start<end && array[end]>=tmp){
                end--;
            }
            //从始端开始遍历数组，直到找到比基准值大的元素的下标
            while(start<end && array[start]<=tmp){
                start++;
            }
            //两次循环结束说明分别在始端找到比基准值大的元素以及在末端找到比基准值小的元素,二者交换
            int tmp1=array[start];
            array[start]=array[end];
            array[end]=tmp1;
        }
        //start和end相遇，将基准值和相遇处元素交换，使得中间为基准值，左侧为都比基准值小的元素，右边都为比基准值大的元素
        int tmp2=array[start];
        array[start]=array[i];
        array[i]=tmp2;
        //返回基准值下标
        return start;
    }

    //实现Hoare型快速排序的非递归形式（借助栈实现）
    public static void hoareQuickSort3(int[] array){
        //创建一个栈
        Stack<Integer>stack=new Stack<>();
        int start=0;
        int end=array.length-1;
        int par=hoarePartition3(array,start,end);
        //判断基准值左侧是否有两个以上元素
        if(par>start+1){
            //将左侧部分的首尾元素入栈
            stack.push(start);
            stack.push(end-1);
        }
        //判断基准值右侧是否有两个以上元素
        if(par<end-1) {
            stack.push(par + 1);
            stack.push(end);
        }
        //栈不为空说明未全部分组完毕
        while(!stack.isEmpty()){
            //出栈获取下一个待分组的末端元素
            end=stack.pop();
            //出栈获取下一个待分组的首端元素
            start=stack.pop();
            par=hoarePartition3(array,start,end);
            //判断基准值左侧是否有两个以上元素
            if(par>start+1){
                //将左侧部分的首尾元素入栈
                stack.push(start);
                stack.push(end-1);
            }
            //判断基准值右侧是否有两个以上元素
            if(par<end-1) {
                stack.push(par + 1);
                stack.push(end);
            }
        }
    }

    //调用到的Hoare形式分组方法
    private static int hoarePartition3(int[]array,int start,int end){
        //记录基准值位置下标
        int i=start;
        //将该组元素的起始元素作为基准值
        int tmp=array[start];
        while(start<end){
            //从末端开始遍历数组，直到找到比基准值小的元素的下标
            //start<end目的是防止下标越界
            //取大于等于或者小于等于的目的是防止进入死循环
            //先走末端因为若先走始端会出现相遇的地方为比基准值大的情况
            while(start<end && array[end]>=tmp){
                end--;
            }
            //从始端开始遍历数组，直到找到比基准值大的元素的下标
            while(start<end && array[start]<=tmp){
                start++;
            }
            //两次循环结束说明分别在始端找到比基准值大的元素以及在末端找到比基准值小的元素,二者交换
            int tmp1=array[start];
            array[start]=array[end];
            array[end]=tmp1;
        }
        //start和end相遇，将基准值和相遇处元素交换，使得中间为基准值，左侧为都比基准值小的元素，右边都为比基准值大的元素
        int tmp2=array[start];
        array[start]=array[i];
        array[i]=tmp2;
        //返回基准值下标
        return start;
    }

}
